package algorithm.leetcode.I1001to1200;


/**
 * 有点像股票交易问题 Q123, 多个状态dp
 */

// 入\出  未删   删过
// 未删   不动   删1
// 删过   N/A   不动

public class Q1186 {

    public int maximumSum(int[] arr) {
        if (arr.length == 1) return arr[0];
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        int[] delDp = new int[arr.length];
        delDp[0] = arr[0];
        int maxVal = Integer.MIN_VALUE;

        for (int i = 1; i < dp.length; i++) {
            // 未删过的状态只能由未删过的状态转移而来(上面矩阵纵列头尾未删列)
            dp[i] = Math.max(dp[i-1]+arr[i], arr[i]);

            // 删过的状态可以由未删过并且删除当前元素,以及,以前就删过不动转移而来(上面矩阵纵列头尾删过列)
            delDp[i] = Math.max(delDp[i-1]+arr[i], dp[i-1]);
            maxVal = Math.max(maxVal, Math.max(delDp[i], dp[i]));
        }
        return maxVal;
    }

}
